#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        size_t n = size(digits);
        digits[n - 1] += 1;
        int k = n - 1;
        while (k >= 0)
        {
            if (digits[k] > 9)
            {
                if (k - 1 < 0)
                {
                    digits.push_back(0);
                    digits[0] = 1;
                    break;
                }
                else
                {
                    digits[k] = 0;
                    digits[k - 1] += 1;
                    k--;
                }
            }
            else
            {
                break;
            }
        }
        return digits;
    }
};

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5) {
                ++ans;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1)
        {
            return x;
        }
        long long i = 0;
        for (; i <= x; i++)
        {
            if (i * i == x)
            {
                return i;
            }
            else if (i * i > x)
            {
                return i - 1;
            }
        }
        return 0;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1)
        {
            return x;
        }
        int left = 0;
        int right = x;
        int p = 0;
        while (left <= right)
        {
            int mid = (right - left) / 2 + left;
            if ((long long)mid * mid <= x)
            {
                p = mid;
                left = p + 1;
            }
            else
            {
                p = mid - 1;
                right = mid - 1;
            }
        }
        return p;
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        if (x == 1 || x == 0)
        {
            return x;
        }
        double num = 1;
        if (n < 0)
        {
            n = -n;
            while (n--)
            {
                num = num * (1 / x);
            }
        }
        else
        {
            while (n--)
            {
                num = num * x;
            }
        }
        return num;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* inorder(const vector<int>& nums, int left, int right)
    {
        if (left > right)
        {
            return nullptr;
        }
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = inorder(nums, left, mid - 1);
        root->right = inorder(nums, mid + 1, right);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return inorder(nums, 0, nums.size() - 1);
    }
};